package Year21_Month11.day1119;

import javax.swing.*;

public class QuickSort {

    public static void quickSort(int[] arr,int left,int right){
        if(right - left > 1) {
            int subscript = partition3(arr, left, right);
            //左边都小于sub[ , )
            quickSort(arr, left, subscript);//注意这里的中间值是取
            //右边都大于sub[ , )
            quickSort(arr, subscript + 1, right);
        }
    }
    public static int partition3(int[] arr,int left,int right){
        int index = right - 1;
        int key = arr[right - 1];
        int cur = left;
        int prev = cur - 1;
        while(cur < right){
            if(arr[cur] < key && ++prev != cur){
                swap(arr,cur,prev);
            }
            cur++;
        }
        if(++prev != cur){
            swap(arr,prev,right - 1);
        }
        return prev;

    }
    public static int partition2(int[] array, int left, int right) {
        //用来比较的值的下标
        int index = right - 1;
        //这里并不多余，再讲一次
        int key = array[right - 1];
        int begin = left;
        int end = right - 1;

        while (begin < end) {
            // 让begin从前往后找比基准值大的元素
            while (begin < end && array[begin] <= key) {
                begin++;
            }
            if (begin < end) {
                // begin位置找到了一个比key大的元素，填end位置的坑
                array[end] = array[begin];
                // begin位置就形成一个新的坑位
            }
            // 让end从后往前找比基准值小的元素
            while (begin < end && array[end] >= key) {
                end--;
            }
            if (begin < end) {
                // end位置找到了一个比key小的元素，填begin位置的坑
                array[begin] = array[end];

                // end位置就形成了一个新的坑位
            }
        }
        array[begin] = key;
        return begin;
    }

    public static int partition1(int[] arr,int left,int right){
        int index = right - 1;
        //等下即将返回的值
        int key = arr[right - 1]; //定义比较元素
        int begin = left;//左边从left开始
        int end = right - 1;//右边从right - 1下标开始

        while(begin < end){
            while(begin < end && arr[begin] <= key){
                begin++;
            }
            while(begin < end && arr[end] >= key){
                end--;
            }
            if(begin != end) {
                swap(arr, begin, end);
            }
        }
        if(begin != right-1){
            swap(arr, begin, right-1);
        }
        return begin;
    }

    public static void swap(int[] arr,int left,int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    public static void print(int[] arr){
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
    public static int getMiddle(int[] array, int left, int right){
            int mid = left + ((right-left)>>1);
        if(array[left] < array[right-1]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right-1]){
                return right-1;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right-1]){
                return right-1;
            }else{
                return mid;
            }
        }
    }
    public static void main(String[] args) {
        int[] array = {4,2,8,6,9,1,3,7,0,5};
        quickSort(array,0,array.length);
        print(array);
    }
}
